11180. Система счисления i - 1

Любое комплексное число n = a + bi может быть однозначно записано в системе счисления i – 1 (i – мнимая единица, i² = -1). То есть существуют такие цифры b_i, равные 0 или 1, что для некоторого натурального k имеет место соотношение:

n = b₀ + b₁(i – 1) + b₂ (i – 1)² + b₃ (i – 1)³ + … + b_k (i – 1)^k

Вход. Первая строка содержит количество тестов t. Каждая из следующих t строк содержит два числа a и b (-10⁶ £ a, b £ 10⁶).

Выход. Для каждого входного комплексного числа a + bi вывести его представление в системе счисления по основанию i – 1.

Пример входа

4

1 0

2 3

11 0

0 0

Пример выхода

Case #1: 1

Case #2: 1011

Case #3: 111001101

Case #4: 0

РЕШЕНИЕ

алгебра

Анализ алгоритма

Рассмотрим условие, при котором число a + bi делится на i – 1 нацело. Имеем:

= = = = +

Отсюда заключаем, что a + bi делится нацело на i – 1 если (a – b) и (a + b) делятся на 2. Последнее имеет место, когда a и b имеют одинаковую четность.

Таким образом, если a и b имеют одинаковую четность, то положим очередное значение цифры результата b_i равным 0, иначе 1. Если a + bi не делится на i – 1, то вычитаем из него 1, после чего (a – 1) + bi уже будет делиться на i – 1. Делим текущее значение комплексного числа на i – 1. Процесс деления продолжаем до тех пор, пока значение a + bi не станет равным 1. Последней цифрой результата b_k будет 1, обращаем строку цифр b_i и выводим ее на печать.

Отдельно следует обработать случай, когда a + bi = 0 + 0*i.

Пример

Рассмотрим второй тест. Запишем число 2 + 3i в системе счисления i – 1. Согласно формуле имеем:

a + bi	бит ответа
2 + 3i	1	= 1 – 2i
1 – 2i	1	= –1 + i
–1 + i	0	= 1 + 0i
1 + 0i	1	стоп

Таким образом 2 + 3i = 1011.

Реализация алгоритма

Читаем количество тестов tests. Для каждого теста читаем значения a и b.

scanf("%d",&tests);

for(i = 0; i < tests; i++)

{

scanf("%d %d",&a,&b);

Отдельно обрабатываем случай, когда a = 0 и b = 0.

if ((a == 0) && (b == 0))

{

printf("Case #%d: 0\n",i+1);

continue;

}

В строке s накапливаем цифры результата, инициализируем ее пустой строкой. Пока a + bi ¹ 1, совершаем деление a + bi на i – 1. Если a и b имеют одинаковую четность, то положим очередную цифру результата равной 0, иначе 1. Пересчитываем значения a и b.

s = "";

while (!((a == 1) && (b == 0)))

{

if ((a + b) % 2) a -= 1,s += '1'; else s += '0';

temp = (b - a) / 2;

b = (a + b) / -2;

a = temp;

}

Добавим в конец строки 1, обернем ее и выведем на печать.

s += '1';

reverse(s.begin(),s.end());

printf("Case #%d: %s\n",i+1,s.c_str());

}